Meeting Pearls 1

home *** CD-ROM | disk | FTP | other *** search

/ Meeting Pearls 1 / Meeting Pearls Vol 1 (1994).iso / installed_progs / text / faqs / cryptography-faq.rsa.part3 < prev next >

Wrap

Internet Message Format | 1994-05-01 | 51.8 KB

Subject: RSA Cryptography Today FAQ (3/3) Newsgroups: sci.crypt,talk.politics.crypto,alt.security.ripem,sci.answers,talk.answers,alt.answers,news.answers From: faq-editor@rsa.com Date: 29 Apr 1994 21:58:27 GMT Archive-name: cryptography-faq/rsa/part3 Last-modified: 93/09/20 Version: 2.0 (This document has been brought to you in part by CRAM. See the bottom for more information, including instructions on how to obtain updates.) === Answers To FREQUENTLY ASKED QUESTIONS About Today's Cryptography Paul Fahn RSA Laboratories 100 Marine Parkway Redwood City, CA 94065 Copyright (c) 1993 RSA Laboratories, a division of RSA Data Security, Inc. All rights reserved. Version 2.0, draft 2f Last update: September 20, 1993 ------------------------------------------------------------------------ Table of Contents [part 3] 6 Capstone, Clipper, and DSS 6.1 What is Capstone? 6.2 What is Clipper? 6.3 How does the Clipper chip work? 6.4 Who are the escrow agencies? 6.5 What is Skipjack? 6.6 Why is Clipper controversial? 6.7 What is the current status of Clipper? 6.8 What is DSS? 6.9 Is DSS secure? 6.10 Is use of DSS covered by any patents? 6.11 What is the current status of DSS? 7 NIST and NSA 7.1 What is NIST? 7.2 What role does NIST play in cryptography? 7.3 What is the NSA? 7.4 What role does the NSA play in commercial cryptography? 8 Miscellaneous 8.1 What is the legal status of documents signed with digital signatures? 8.2 What is a hash function? What is a message digest? 8.3 What are MD2, MD4 and MD5? 8.4 What is SHS? 8.5 What is Kerberos? 8.6 What are RC2 and RC4? 8.7 What is PEM? 8.8 What is RIPEM? 8.9 What is PKCS? 8.10 What is RSAREF? -------------------------------------------------------------------- 6 Capstone, Clipper, and DSS 6.1 What is Capstone? Capstone is the U.S. government's long-term project to develop a set of standards for publicly-available cryptography, as authorized by the Computer Security Act of 1987. The primary agencies responsible for Capstone are NIST and the NSA (see Section 7). The plan calls for the elements of Capstone to become official U.S. government standards, in which case both the government itself and all private companies doing business with the government would be required to use Capstone. There are four major components of Capstone: a bulk data encryption algorithm, a digital signature algorithm, a key exchange protocol, and a hash function. The data encryption algorithm is called Skipjack (see Question 6.5), but is often referred to as Clipper, which is the encryption chip that includes Skipjack (see Question 6.2). The digital signature algorithm is DSS (see Question 6.8) and the hash function is SHS (see Question 8.4 about SHS and Question 8.2 about hash functions). The key exchange protocol has not yet been announced. All the parts of Capstone have 80-bit security: all the keys involved are 80 bits long and other aspects are also designed to withstand anything less than an ``80-bit'' attack, that is, an effort of 2^{80} operations. Eventually the government plans to place the entire Capstone cryptographic system on a single chip. 6.2 What is Clipper? Clipper is an encryption chip developed and sponsored by the U.S. government as part of the Capstone project (see Question 6.1). Announced by the White House in April, 1993 [65], Clipper was designed to balance the competing concerns of federal law-enforcement agencies with those of private citizens and industry. The law-enforcement agencies wish to have access to the communications of suspected criminals, for example by wire-tapping; these needs are threatened by secure cryptography. Industry and individual citizens, however, want secure communications, and look to cryptography to provide it. Clipper technology attempts to balance these needs by using escrowed keys. The idea is that communications would be encrypted with a secure algorithm, but the keys would be kept by one or more third parties (the ``escrow agencies''), and made available to law-enforcement agencies when authorized by a court-issued warrant. Thus, for example, personal communications would be impervious to recreational eavesdroppers, and commercial communications would be impervious to industrial espionage, and yet the FBI could listen in on suspected terrorists or gangsters. Clipper has been proposed as a U.S. government standard [62]; it would then be used by anyone doing business with the federal government as well as for communications within the government. For anyone else, use of Clipper is strictly voluntary. AT&T has announced a secure telephone that uses the Clipper chip. 6.3 How does the Clipper chip work? The Clipper chip contains an encryption algorithm called Skipjack (see Question 6.5}), whose details have not been made public. Each chip also contains a unique 80-bit unit key U, which is escrowed in two parts at two escrow agencies; both parts must be known in order to recover the key. Also present is a serial number and an 80-bit ``family key'' F; the latter is common to all Clipper chips. The chip is manufactured so that it cannot be reverse engineered; this means that the Skipjack algorithm and the keys cannot be read off the chip. When two devices wish to communicate, they first agree on an 80-bit ``session key'' K. The method by which they choose this key is left up to the implementer's discretion; a public-key method such as RSA or Diffie-Hellman seems a likely choice. The message is encrypted with the key K and sent; note that the key K is not escrowed. In addition to the encrypted message, another piece of data, called the law-enforcement access field (LEAF), is created and sent. It includes the session key K encrypted with the unit key U, then concatenated with the serial number of the sender and an authentication string, and then, finally, all encrypted with the family key. The exact details of the law-enforcement field are classified. The receiver decrypts the law-enforcement field, checks the authentication string, and decrypts the message with the key K. Now suppose a law-enforcement agency wishes to tap the line. It uses the family key to decrypt the law-enforcement field; the agency now knows the serial number and has an encrypted version of the session key. It presents an authorization warrant to the two escrow agencies along with the serial number. The escrow agencies give the two parts of the unit key to the law-enforcement agency, which then decrypts to obtain the session key K. Now the agency can use K to decrypt the actual message. Further details on the Clipper chip operation, such as the generation of the unit key, are sketched by Denning [26]. 6.4 Who are the escrow agencies? It has not yet been decided which organizations will serve as the escrow agencies, that is, keep the Clipper chip keys. No law-enforcement agency will be an escrow agency, and it is possible that at least one of the escrow agencies will be an organization outside the government. It is essential that the escrow agencies keep the key databases extremely secure, since unauthorized access to both escrow databases could allow unauthorized eavesdropping on private communications. In fact, the escrow agencies are likely to be one of the major targets for anyone trying to compromise the Clipper system; the Clipper chip factory is another likely target. 6.5 What is Skipjack? Skipjack is the encryption algorithm contained in the Clipper chip; it was designed by the NSA. It uses an 80-bit key to encrypt 64-bit blocks of data; the same key is used for the decryption. Skipjack can be used in the same modes as DES (see Question 5.3), and may be more secure than DES, since it uses 80-bit keys and scrambles the data for 32 steps, or ``rounds''; by contrast, DES uses 56-bit keys and scrambles the data for only 16 rounds. The details of Skipjack are classified. The decision not to make the details of the algorithm publicly available has been widely criticized. Many people are suspicious that Skipjack is not secure, either due to oversight by its designers, or by the deliberate introduction of a secret trapdoor. By contrast, there have been many attempts to find weaknesses in DES over the years, since its details are public. These numerous attempts (and the fact that they have failed) have made people confident in the security of DES. Since Skipjack is not public, the same scrutiny cannot be applied towards it, and thus a corresponding level of confidence may not arise. Aware of such criticism, the government invited a small group of independent cryptographers to examine the Skipjack algorithm. They issued a report [12] which stated that, although their study was too limited to reach a definitive conclusion, they nevertheless believe that Skipjack is secure. Another consequence of Skipjack's classified status is that it cannot be implemented in software, but only in hardware by government-authorized chip manufacturers. 6.6 Why is Clipper controversial? The Clipper chip proposal has aroused much controversy and has been the subject of much criticism. Unfortunately two distinct issues have become confused in the large volume of public comment and discussion. First there is controversy about the whole idea of escrowed keys. Those in favor of escrowed keys see it as a way to provide secure communications for the public at large while allowing law-enforcement agencies to monitor the communications of suspected criminals. Those opposed to escrowed keys see it as an unnecessary and ineffective intrusion of the government into the private lives of citizens. They argue that escrowed keys infringe their rights of privacy and free speech. It will take a lot of time and much public discussion for society to reach a consensus on what role, if any, escrowed keys should have. The second area of controversy concerns various objections to the specific Clipper proposal, that is, objections to this particular implementation of escrowed keys, as opposed to the idea of escrowed keys in general. Common objections include: the Skipjack algorithm is not public (see Questions 6.5) and may not be secure; the key escrow agencies will be vulnerable to attack; there are not enough key escrow agencies; the keys on the Clipper chips are not generated in a sufficiently secure fashion; there will not be sufficient competition among implementers, resulting in expensive and slow chips; software implementations are not possible; and the key size is fixed and cannot be increased if necessary. Micali [55] has recently proposed an alternative system that also attempts to balance the privacy concerns of law-abiding citizens with the investigative concerns of law-enforcement agencies. Called fair public-key cryptography, it is similar in function and purpose to the Clipper chip proposal but users can choose their own keys, which they register with the escrow agencies. Also, the system does not require secure hardware, and can be implemented completely in software. 6.7 What is the current status of Clipper? Clipper is under review. Both the executive branch and Congress are considering it, and an advisory panel recently recommended a full year-long public discussion of cryptography policy. NIST has invited the public to send comments, as part of its own review. 6.8 What is DSS? DSS is the proposed Digital Signature Standard, which specifies a Digital Signature Algorithm (DSA), and is a part of the U.S. government's Capstone project (see Question 6.1). It was selected by NIST, in cooperation with the NSA (see Section 7), to be the digital authentication standard of the U.S. government; whether the government should in fact adopt it as the official standard is still under debate. DSS is based on the discrete log problem (see Question 4.9) and derives from cryptosystems proposed by Schnorr [75] and ElGamal [30]. It is for authentication only. For a detailed description of DSS, see [63] or [57]. DSS has, for the most part, been looked upon unfavorably by the computer industry, much of which had hoped the government would choose the RSA algorithm as the official standard; RSA is the most widely used authentication algorithm. Several articles in the press, such as [54], discuss the industry dissatisfaction with DSS. Criticism of DSS has focused on a few main issues: it lacks key exchange capability; the underlying cryptosystem is too recent and has been subject to too little scrutiny for users to be confident of its strength; verification of signatures with DSS is too slow; the existence of a second authentication standard will cause hardship to computer hardware and software vendors, who have already standardized on RSA; and that the process by which NIST chose DSS was too secretive and arbitrary, with too much influence wielded by NSA. Other criticisms were addressed by NIST by modifying the original proposal. A more detailed discussion of the various criticisms can be found in [57], and a detailed response by NIST can be found in [78]. In the DSS system, signature generation is faster than signature verification, whereas in the RSA system, signature verification is faster than signature generation (if the public and private exponents are chosen for this property, which is the usual case). NIST claims that it is an advantage of DSS that signing is faster, but many people in cryptography think that it is better for verification to be the faster operation. 6.9 Is DSS secure? The most serious criticisms of DSS involve its security. DSS was originally proposed with a fixed 512-bit key size. After much criticism that this is not secure enough, NIST revised DSS to allow key sizes up to 1024 bits. More critical, however, is the fact that DSS has not been around long enough to withstand repeated attempts to break it; although the discrete log problem is old, the particular form of the problem used in DSS was first proposed for cryptographic use in 1989 by Schnorr [75] and has not received much public study. In general, any new cryptosystem could have serious flaws that are only discovered after years of scrutiny by cryptographers. Indeed this has happened many times in the past; see [13] for some detailed examples. RSA has withstood over 15 years of vigorous examination for weaknesses. In the absence of mathematical proofs of security, nothing builds confidence in a cryptosystem like sustained attempts to crack it. Although DSS may well turn out to be a strong cryptosystem, its relatively short history will leave doubts for years to come. Some researchers warned about the existence of ``trapdoor'' primes in DSS, which could enable a key to be easily broken. These trapdoor primes are relatively rare however, and are easily avoided if proper key generation procedures are followed [78]. 6.10 Is use of DSS covered by any patents? NIST has filed a patent application for DSS and there have been claims that DSS is covered by other public-key patents. NIST recently announced its intention to grant exclusive sublicensing rights for the DSS patent to Public Key Partners (PKP), which also holds the sublicensing rights to other patents that may cover DSS (see Question 1.5). In the agreement between NIST and PKP, PKP publicly stated uniform guidelines by which it will grant licenses to practice DSS. PKP stated that DSS can be used on a royalty-free basis in the case of personal, noncommercial, or U.S. government use. See [61] for details on the agreement and the licensing policy. 6.11 What is the current status of DSS? After NIST issued the DSS proposal in August 1991, there was a period in which comments from the public were solicited; NIST then revised its proposal in light of the comments. DSS may be issued as a FIPS and become the official U.S. government standard, but it is not clear when this might happen. DSS is currently in the process of becoming a standard, along with RSA, for the financial services industry; a recent draft standard [1] contains the revised version of DSS. 7 NIST and NSA 7.1 What is NIST? NIST is an acronym for the National Institute of Standards and Technology, a division of the U.S. Department of Commerce; it was formerly known as the National Bureau of Standards (NBS). Through its Computer Systems Laboratory it aims to promote open systems and interoperability that will spur development of computer-based economic activity. NIST issues standards and guidelines that it hopes will be adopted by all computer systems in the U.S., and also sponsors workshops and seminars. Official standards are published as FIPS (Federal Information Processing Standards) publications. In 1987 Congress passed the Computer Security Act, which authorized NIST to develop standards for ensuring the security of sensitive but unclassified information in government computer systems. It encouraged NIST to work with other government agencies and private industry in evaluating proposed computer security standards. 7.2 What role does NIST play in cryptography? NIST issues standards for cryptographic routines; U.S. government agencies are required to use them, and the private sector often adopts them as well. In January 1977, NIST declared DES (see Question 5.1) the official U.S. encryption standard and published it as FIPS Publication 46; DES soon became a de facto standard throughout the U.S. A few years ago, NIST was asked to choose a set of cryptographic standards for the U.S.; this has become known as the Capstone project (see Section 6). After a few years of rather secretive deliberations, and in cooperation with the NSA, NIST issued proposals for various standards in cryptography, including digital signatures (DSS) and data encryption (the Clipper chip); these are pieces of the overall Capstone project. NIST has been criticized for allowing the NSA too much power in setting cryptographic standards, since the interests of the NSA conflict with that of the Commerce Department and NIST. Yet, the NSA has much more experience with cryptography, and many more qualified cryptographers and cryptanalysts, than does NIST; it would be unrealistic to expect NIST to forego such available assistance. 7.3 What is the NSA? The NSA is the National Security Agency, a highly secretive agency of the U.S. government that was created by Harry Truman in 1952; its very existence was kept secret for many years. For a history of the NSA, see Bamford [2]. The NSA has a mandate to listen to and decode all foreign communications of interest to the security of the United States. It has also used its power in various ways (see Question 7.4) to slow the spread of publicly available cryptography, in order to prevent national enemies from employing encryption methods too strong for the NSA to break. As the premier cryptographic government agency, the NSA has huge financial and computer resources and employs a host of cryptographers. Developments in cryptography achieved at the NSA are not made public; this secrecy has led to many rumors about the NSA's ability to break popular cryptosystems like DES and also to rumors that the NSA has secretly placed weaknesses, called trap doors, in government-endorsed cryptosystems, such as DES. These rumors have never been proved or disproved, and the criteria used by the NSA in selecting cryptography standards have never been made public. Recent advances in the computer and telecommunications industries have placed NSA actions under unprecedented scrutiny, and the agency has become the target of heavy criticism for hindering U.S. industries that wish to use or sell strong cryptographic tools. The two main reasons for this increased criticism are the collapse of the Soviet Union and the development and spread of commercially available public-key cryptographic tools. Under pressure, the NSA may be forced to change its policies. 7.4 What role does the NSA play in commercial cryptography? The NSA's charter limits its activities to foreign intelligence. However, the NSA is concerned with the development of commercial cryptography because the availability of strong encryption tools through commercial channels could impede the NSA's mission of decoding international communications; in other words, the NSA is worried lest strong commercial cryptography fall into the wrong hands. The NSA has stated that it has no objection to the use of secure cryptography by U.S. industry. It also has no objection to cryptographic tools used for authentication, as opposed to privacy. However, the NSA is widely viewed as following policies that have the practical effect of limiting and/or weakening the cryptographic tools used by law-abiding U.S. citizens and corporations; see Barlow [3] for a discussion of NSA's effect on commercial cryptography. The NSA exerts influence over commercial cryptography in several ways. First, it controls the export of cryptography from the U.S. (see Question 1.6); the NSA generally does not approve export of products used for encryption unless the key size is strictly limited. It does, however, approve for export any products used for authentication only, no matter how large the key size, so long as the product cannot be converted to be used for encryption. The NSA has also blocked encryption methods from being published or patented, citing a national security threat; see Landau [46] for a discussion of this practice. Additionally, the NSA serves an ``advisory'' role to NIST in the evaluation and selection of official U.S. government computer security standards; in this capacity, it has played a prominent, and controversial, role in the selection of DES and in the development of the group of standards known as the Capstone project (see Section 6), which includes DSS and the Clipper chip. The NSA can also exert market pressure on U.S. companies to produce (or refrain from producing) cryptographic goods, since the NSA itself is often a large customer of these companies. Cryptography is in the public eye as never before and has become the subject of national public debate. The status of cryptography, and the NSA's role in it, will probably change over the next few years. 8 Miscellaneous 8.1 What is the legal status of documents signed with digital signatures? If digital signatures are to replace handwritten signatures they must have the same legal status as handwritten signatures, i.e., documents signed with digital signatures must be legally binding. NIST has stated that its proposed Digital Signature Standard (see Question 6.8) should be capable of ``proving to a third party that data was actually signed by the generator of the signature.'' Furthermore, U.S. federal government purchase orders will be signed by any such standard; this implies that the government will support the legal authority of digital signatures in the courts. Some preliminary legal research has also resulted in the opinion that digital signatures would meet the requirements of legally binding signatures for most purposes, including commercial use as defined in the Uniform Commercial Code (UCC). A GAO (Government Accounting Office) decision requested by NIST also opines that digital signatures will meet the legal standards of handwritten signatures [20]. However, since the validity of documents with digital signatures has never been challenged in court, their legal status is not yet well-defined. Through such challenges, the courts will issue rulings that collectively define which digital signature methods, key sizes, and security precautions are acceptable for a digital signature to be legally binding. Digital signatures have the potential to possess greater legal authority than handwritten signatures. If a ten-page contract is signed by hand on the tenth page, one cannot be sure that the first nine pages have not been altered. If the contract was signed by digital signatures, however, a third party can verify that not one byte of the contract has been altered. Currently, if two people wish to digitally sign a series of contracts, they may wish to first sign a paper contract in which they agree to be bound in the future by any contracts digitally signed by them with a given signature method and minimum key size. 8.2 What is a hash function? What is a message digest? A hash function is a computation that takes a variable-size input and returns a fixed-size string, which is called the hash value. If the hash function is one-way, i.e., hard to invert, it is also called a message-digest function, and the result is called a message digest. The idea is that a digest represents concisely the longer message or document from which it was computed; one can think of a message digest as a ``digital fingerprint'' of the larger document. Examples of well-known hash functions are MD4, MD5, and SHS (see Questions 8.3 and 8.4). Although hash functions in general have many uses in computer programs, in cryptography they are used to generate a small string (the message digest) that can represent securely a much larger string, such as a file or message. Since the hash functions are faster than the signing functions, it is much more efficient to compute a digital signature using a document's message digest, which is small, than using the arbitrarily large document itself. Additionally, a digest can be made public without revealing the contents of the document from which it derives. This is important in digital time-stamping, where, using hash functions, one can get a document time-stamped without revealing its contents to the time-stamping service (see Question 3.18). A hash function used for digital authentication must have certain properties that make it secure enough for cryptographic use. Specifically, it must be infeasible to find a message that hashes to a given value and it must be infeasible to find two distinct messages that hash to the same value. The ability to find a message hashing to a given value would enable an attacker to substitute a fake message for a real message that was signed. It would also enable someone to falsely disown a message by claiming that he or she actually signed a different message hashing to the same value, thus violating the non-repudiation property of digital signatures. The ability to find two distinct messages hashing to the same value could enable an attack whereby someone is tricked into signing a message which hashes to the same value as another message with a quite different meaning. The digest must therefore be long enough to prevent an attacker from doing an exhaustive search for a collision. For example, if a hash function produces 100-bit strings, exhaustive search would take 2^{100} attempts on average to match a given value, and approximately 2^{50} attempts on average to find two inputs producing the same digest. A digital signature system can be broken by attacking either the difficult mathematical problem on which the signature method is based or the hash function used to create the message digests. When choosing an authentication system, it is generally a good idea to choose a signature method and a hash function that require comparable efforts to break; any extra security in one of the two components is wasted, since attacks will be directed at the weaker component. Actually, attacking the hash function is harder in practice, since it requires a large amount of memory and the ability to trick the victim into signing a special message. With 2^{64} operations, an attacker can find two messages that hash to the same digest under any of the MD hash functions; this effort is comparable to that necessary to break 512-bit RSA; thus MD5 is a good choice when using RSA with a 512-bit modulus. However, those with greater security needs, such as certifying authorities, should use a longer modulus and a hash function that produces a longer message digest; either SHS (160-bit digest) or a modified version of MD4 that produces a 256-bit digest [71] would suffice. 8.3 What are MD2, MD4 and MD5? MD2, MD4 and MD5 (MD stands for Message Digest) are widely used hash functions designed by Ron Rivest specifically for cryptographic use. They produce 128-bit digests and there is no known attack faster than exhaustive search. MD2 is the slowest of the three; MD4 [71] is the fastest. MD5 [73] has been dubbed ``MD4 with safety belts'' by Rivest, since it has a more conservative design than MD4; the design gives it increased security against attack, but at a cost of being approximately 33% slower than MD4. MD5 is the most commonly used of the three algorithms. MD4 and MD5 are publicly available for unrestricted use; MD2 is available for use with PEM (see Question 8.7). Details of MD2, MD4, and MD5 with sample C code are available in Internet RFCs (Requests For Comments) 1319, 1320, and 1321, respectively. No feasible attacks on any of the MD algorithms have been discovered, although some recent theoretical work has found some interesting structural properties [24,25]. 8.4 What is SHS? The Secure Hash Standard (SHS) [58] is a hash function proposed by NIST (see Question 7.1) and adopted as a U.S. government standard. It is designed for use with the proposed Digital Signature Standard (see Question 6.8) and is part of the government's Capstone project (see Question 6.1}). SHS produces a 160-bit hash value from a variable-size input. SHS is structurally similar to MD4 and MD5. It is roughly 25% slower than MD5 but may be more secure, because it produces message digests that are 25% longer than those produced by the MD functions. SHS is currently the only part of Capstone that has been officially adopted as a government standard. 8.5 What is Kerberos? Kerberos is a secret-key network authentication system developed at MIT [79]; it uses DES for encryption and authentication. Unlike a public-key authentication system, it does not produce digital signatures: Kerberos was designed to authenticate requests for network resources rather than to authenticate authorship of documents. Kerberos provides real-time authentication in a distributed environment, but does not provide for future third-party verification of documents. In a Kerberos system, there is a designated site on the network, called the Kerberos server, which performs centralized key management and administrative functions. The server maintains a database containing the secret keys of all users, generates session keys whenever two users wish to communicate securely, and authenticates the identity of a user who requests certain network services. Kerberos, like other secret-key systems, requires trust in a third party, in this case the Kerberos server. If the server were compromised, the integrity of the whole system would fall. Public-key cryptography was designed precisely to avoid the necessity to trust third parties or communication lines (see Question 1.4). Kerberos may be adequate for those who do not need the more robust functions and properties of public-key systems. 8.6 What are RC2 and RC4? RC2 and RC4 are variable-key-size cipher functions designed by Ron Rivest for fast bulk encryption. They are alternatives to DES (see Question 5.1) and are as fast or faster than DES. They can be more secure than DES because of their ability to use long key sizes; they can also be less secure than DES if short key sizes are used. RC2 is a variable-key-size symmetric block cipher and can serve as a drop-in replacement for DES, for example in export versions of products otherwise using DES. RC2 can be used in the same modes as DES (see Question 5.3), including triple encryption. RC2 is approximately twice as fast as DES, at least in software. RC4 is a variable-key-size symmetric stream cipher and is 10 or more times as fast as DES in software. Both RC2 and RC4 are very compact in terms of code size. An agreement between the Software Publishers Association (SPA) and the U.S. government gives RC2 and RC4 special status by means of which the export approval process is simpler and quicker than the usual cryptographic export process. However, to qualify for quick export approval a product must limit the RC2 and RC4 key sizes to 40 bits; 56 bits is allowed for foreign subsidiaries and overseas offices of U.S. companies. An additional 40-bit string, called a salt, can be used to thwart attackers who try to precompute a large look-up table of possible encryptions. The salt is appended to the encryption key, and this lengthened key is used to encrypt the message; the salt is then sent, unencrypted, with the message. RC2 and RC4 have been widely used by developers who want to export their products; DES is almost never approved for export. RC2 and RC4 are proprietary algorithms of RSA Data Security, Inc.; details have not been published. 8.7 What is PEM? PEM is the Internet Privacy-Enhanced Mail standard, designed, proposed, but not yet officially adopted, by the Internet Activities Board in order to provide secure electronic mail over the Internet. Designed to work with current Internet e-mail formats, PEM includes encryption, authentication, and key management, and allows use of both public-key and secret-key cryptosystems. Multiple cryptographic tools are supported: for each mail message, the specific encryption algorithm, digital signature algorithm, hash function, and so on are specified in the header. PEM explicitly supports only a few cryptographic algorithms; others may be added later. DES in CBC mode is currently the only message encryption algorithm supported, and both RSA and DES are supported for the key management. PEM also supports the use of certificates, endorsing the CCITT X.509 standard for certificate structure. The details of PEM can be found in Internet RFCs (Requests For Comments) 1421 through 1424. PEM is likely to be officially adopted by the Internet Activities Board within one year. Trusted Information Systems has developed a free non-commercial implementation of PEM, and other implementations should soon be available as well. 8.8 What is RIPEM? RIPEM is a program developed by Mark Riordan that enables secure Internet e-mail; it provides both encryption and digital signatures, using RSA and DES routines from RSAREF (see Question 8.10). RIPEM is not fully PEM-compatible; for example, it does not currently support certificates. However, future versions will include certificates and will be fully compliant with the PEM standard. RIPEM is available free for non-commercial use in the U.S. and Canada. To get RIPEM, obtain an ftp account at ripem.msu.edu. 8.9 What is PKCS? PKCS (Public-Key Cryptography Standards) is a set of standards for implementation of public-key cryptography. It has been issued by RSA Data Security, Inc. in cooperation with a computer industry consortium, including Apple, Microsoft, DEC, Lotus, Sun and MIT. PKCS has been cited by the OIW (OSI Implementors' Workshop) as a method for implementation of OSI standards. PKCS is compatible with PEM (see Question 8.7) but extends beyond PEM. For example, where PEM can only handle ASCII data, PKCS is designed for binary data as well. PKCS is also compatible with the CCITT X.509 standard. PKCS includes both algorithm-specific and algorithm-independent implementation standards. Specific algorithms supported include RSA, DES, and Diffie-Hellman key exchange. It also defines algorithm-independent syntax for digital signatures, digital envelopes (for encryption), and certificates; this enables someone implementing any cryptographic algorithm whatsoever to conform to a standard syntax and thus preserve interoperability. Documents detailing the PKCS standards can be obtained by sending e-mail to pkcs@rsa.com or by anonymous ftp to rsa.com. 8.10 What is RSAREF? RSAREF is a collection of cryptographic routines in portable C source code, available at no charge from RSA Laboratories, a division of RSA Data Security, Inc. It includes RSA, MD2, MD5, and DES; Diffie-Hellman key exchange will be included in a forthcoming version. It includes both low-level subroutines, such as modular exponentiation, and high-level cryptographic functions, such as verification of digital signatures. The arithmetic routines can handle multiple-precision integers, and the RSA algorithm routines can handle variable key sizes. RSAREF is fully compatible with the PEM and PKCS standards. RSAREF is available to citizens of the U.S. or Canada and to permanent residents of the U.S. It can be used in personal, non-commercial applications but cannot be used commercially or sent outside the U.S. and Canada. The RSAREF license contains more details on the usage allowed and disallowed. RSAREF is available on the Internet by sending e-mail to rsaref@rsa.com or by ftp to rsa.com. 9 Acknowledgements I would like to thank the following people, who have provided information and helpful suggestions: Burt Kaliski, Jim Bidzos, Matt Robshaw, Steve Dusse, Kurt Stammberger, George Parsons, John Gilmore, Stuart Haber, Dorothy Denning, and Dennis Branstad. BIBLIOGRAPHY 1. American National Standards Institute. Working Draft: American National Standard X9.30-199X: Public Key Cryptography Using Irreversible Algorithms for the Financial Services Industry: Part 1: The Digital Signature Algorithm (DSA). American Bankers Association, Washington, D.C., March 4, 1993. 2. J. Bamford. The Puzzle Palace. Houghton Mifflin, Boston, 1982. 3. J.P. Barlow. Decrypting the puzzle palace. Communications of the ACM, 35(7):25--31, July 1992. 4. D. Bayer, S. Haber, and W.S. Stornetta. Improving the efficiency and reliablility of digital time-stamping. In R.M. Capocelli, editor, Sequences '91: Methods in Communication, Security, and Computer Science, Springer-Verlag, Berlin, 1992. 5. P. Beauchemin, G. Brassard, C. Crepeau, C. Goutier, and C. Pomerance. The generation of random numbers that are probably prime. J. of Cryptology, 1:53--64, 1988. 6. E. Biham and A. Shamir. Differential Cryptanalysis of the Data Encryption Standard. Springer-Verlag, New York, 1993. 7. E. Biham and A. Shamir. Differential cryptanalysis of the full 16-round DES. In Advances in Cryptology --- Crypto '92, Springer-Verlag, New York, 1993. 8. M. Blum and S. Goldwasser. An efficient probabilistic public-key encryption scheme which hides all partial information. In Advances in Cryptology --- Crypto '84, pages 289--299, Springer-Verlag, New York, 1985. 9. J. Brandt and I. Damgard. On generation of probable primes by incremental search. In Advances in Cryptology --- Crypto '92, Springer-Verlag, New York, 1993. 10. G. Brassard. Modern Cryptology. Volume 325 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1988. 11. D.M. Bressoud. Factorization and Primality Testing. Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1989. 12. E.F. Brickell, D.E. Denning, S.T. Kent, D.P. Maher, and W. Tuchman. Skipjack Review, Interim Report: The Skipjack Algorithm. July 28, 1993. 13. E.F. Brickell and A.M. Odlyzko. Cryptanalysis: A survey of recent results. Proceedings of the IEEE, 76:578--593, 1988. 14. J. Brillhart, D.H. Lehmer, J.L. Selfridge, B. Tuckerman, and S.S. Wagstaff Jr. Factorizations of b^n +/- 1, b=2,3,5,6,7,10,11,12 up to High Powers. Volume 22 of Contemporary Mathematics, American Mathematical Society, Providence, Rhode Island, 2nd edition, 1988. 15. J. Buchmann, J. Loho, and J. Zayer. An implementation of the general number field sieve. In Advances, in Cryptology --- Crypto '93, Springer-Verlag, New York, 1994. To appear. 16. J.P. Buhler, H.W. Lenstra, and C. Pomerance. Factoring integers with the number field sieve. 1992. To appear. 17. M.V.D. Burmester, Y.G. Desmedt, and T. Beth. Efficient zero-knowledge identification schemes for smart cards. Computer Journal, 35:21--29, 1992. 18. K.W. Campbell and M.J. Wiener. Proof that DES is not a group. In Advances in Cryptology --- Crypto '92, Springer-Verlag, New York, 1993. 19. CCITT (Consultative Committee on International Telegraphy and Telephony). Recommendation X.509: The Directory---Authentication Framework. 1988. 20. Comptroller General of the United States. Matter of National Institute of Standards and Technology --- Use of Electronic Data Interchange Technology to Create Valid Obligations. December 13, 1991. File B-245714. 21. D. Coppersmith, A.M. Odlyzko, and R. Schroeppel. Discrete logarithms in GF(p). Algorithmica, 1:1--15, 1986. 22. T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, 1990. 23. G. Davida. Chosen signature cryptanalysis of the RSA public key cryptosystem. Technical Report TR-CS-82-2, Dept of EECS, University of Wisconsin, Milwaukee, 1982. 24. B. den Boer and A. Bosselaers. An attack on the last two rounds of MD4. In Advances in Cryptology --- Crypto '91, pages 194--203, Springer-Verlag, New York, 1992. 25. B. den Boer and A. Bosselaers. Collisions for the compression function of MD5. In Advances in Cryptology --- Eurocrypt '93, 1993. Preprint. 26. Dorothy E. Denning. The Clipper encryption system. American Scientist, 81(4):319--323, July--August 1993. 27. W. Diffie. The first ten years of public-key cryptography. Proceedings of the IEEE, 76:560--577, 1988. 28. W. Diffie and M.E. Hellman. Exhaustive cryptanalysis of the NBS Data Encryption Standard. Computer, 10:74--84, 1977. 29. W. Diffie and M.E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22:644--654, 1976. 30. T. ElGamal. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, IT-31:469--472, 1985. 31. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology --- Crypto '86, pages 186--194, Springer-Verlag, New York, 1987. 32. S. Goldwasser and S. Micali. Probabilistic encryption. J. of Computer and System Sciences, 28:270--299, 1984. 33. D.M. Gordon. Discrete logarithms using the number field sieve. March 28, 1991. To appear. 34. D.M. Gordon and K.S. McCurley. Massively parallel computation of discrete logarithms. In Advances in Cryptology --- Crypto '92, Springer-Verlag, New York, 1993. 35. J. Hastad. Solving simultaneous modular equations of low degree. SIAM J. Computing, 17:336--241, 1988. 36. M.E. Hellman. A cryptanalytic time-memory trade off. IEEE Transactions on Information Theory, IT-26:401--406, 1980. 37. D. Kahn. The Codebreakers. Macmillan Co., New York, 1967. 38. B.S. Kaliski. A survey of encryption standards. RSA Data Security, Inc., September 2, 1993. 39. B.S. Kaliski Jr., R.L. Rivest, and A.T. Sherman. Is the data encryption standard a group? J. of Cryptology, 1:3--36, 1988. 40. S. Kent. RFC 1422: Privacy Enhancement for Internet Electronic Mail, Part II: Certificate-Based Key Management. Internet Activities Board, February 1993. 41. D.E. Knuth. The Art of Computer Programming. Volume 2, Addison-Wesley, Reading, Mass., 2nd edition, 1981. 42. N. Koblitz. A Course in Number Theory and Cryptography. Springer-Verlag, New York, 1987. 43. N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48:203--209, 1987. 44. X. Lai and J.L. Massey. A proposal for a new block encryption standard. In Advances in Cryptology --- Eurocrypt '90, pages 389--404, Springer-Verlag, Berlin, 1991. 45. B.A. LaMacchia and A.M. Odlyzko. Computation of discrete logarithms in prime fields. Designs, Codes and Cryptography, 1:47--62, 1991. 46. S. Landau. Zero knowledge and the Department of Defense. Notices of the American Mathematical Society, 35:5--12, 1988. 47. A.K. Lenstra and H.W. Lenstra Jr. Algorithms in number theory. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, MIT Press/Elsevier, Amsterdam, 1990. 48. A.K. Lenstra, H.W. Lenstra Jr., M.S. Manasse, and J.M. Pollard. The factorization of the ninth Fermat number. 1991. To appear. 49. A.K. Lenstra and M.S. Manasse. Factoring with two large primes. In Advances in Cryptology --- Eurocrypt '90, pages 72--82, Springer-Verlag, Berlin, 1991. 50. H.W. Lenstra Jr. Factoring integers with elliptic curves. Ann. of Math., 126:649--673, 1987. 51. M. Matsui. Linear cryptanalysis method for DES cipher. In Advances in Cryptology --- Eurocrypt '93, Springer-Verlag, Berlin, 1993. To appear. 52. R.C. Merkle and M.E. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, IT-24:525--530, 1978. 53. R.C. Merkle and M.E. Hellman. On the security of multiple encryption. Communications of the ACM, 24:465--467, July 1981. 54. E. Messmer. NIST stumbles on proposal for public-key encryption. Network World, 9(30), July 27, 1992. 55. S. Micali. Fair public-key cryptosystems. In Advances in Cryptology --- Crypto '92, Springer-Verlag, New York, 1993. 56. V.S. Miller. Use of elliptic curves in cryptography. In Advances in Cryptology --- Crypto '85, pages 417--426, Springer-Verlag, New York, 1986. 57. National Institute of Standards and Technology (NIST). The Digital Signature Standard, proposal and discussion. Communications of the ACM, 35(7):36--54, July 1992. 58. National Institute of Standards and Technology (NIST). FIPS Publication 180: Secure Hash Standard (SHS). May 11, 1993. 59. National Institute of Standards and Technology (NIST). FIPS Publication 46-1: Data Encryption Standard. January 22, 1988. Originally issued by National Bureau of Standards. 60. National Institute of Standards and Technology (NIST). FIPS Publication 81: DES Modes of Operation. December 2, 1980. Originally issued by National Bureau of Standards. 61. National Institute of Standards and Technology (NIST). Notice of proposal for grant of exclusive patent license. Federal Register, 58(108), June 8, 1993. 62. National Institute of Standards and Technology (NIST). A proposed Federal Information Processing Standard for an Escrowed Encryption Standard (EES). Federal Register, 58(145), July 30, 1993. 63. National Institute of Standards and Technology (NIST). Publication XX: Announcement and Specifications for a Digital Signature Standard (DSS). August 19, 1992. 64. A.M. Odlyzko. Discrete logarithms in finite fields and their cryptographic significance. In Advances in Cryptology --- Eurocrypt '84, pages 224--314, Springer-Verlag, Berlin, 1984. 65. Office of the Press Secretary. Statement. The White House, April 16, 1993. 66. J. Pollard. Monte Carlo method for factorization. BIT, 15:331--334, 1975. 67. J. Pollard. Theorems of factorization and primality testing. Proc. Cambridge Philos. Soc., 76:521--528, 1974. 68. M.O. Rabin. Digitalized signatures as intractable as factorization. Technical Report MIT/LCS/TR-212, MIT, 1979. 69. R.L. Rivest. Cryptography. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, MIT Press/Elsevier, Amsterdam, 1990. 70. R.L. Rivest. Finding four million random primes. In Advances in Cryptology --- Crypto '90, pages 625--626, Springer-Verlag, New York, 1991. 71. R.L Rivest. The MD4 message digest algorithm. In Advances in Cryptology --- Crypto '90, pages 303--311, Springer-Verlag, New York, 1991. 72. R.L. Rivest. Response to NIST's proposal. Communications of the ACM, 35:41--47, July 1992. 73. R.L. Rivest. RFC 1321: The MD5 Message-Digest Algorithm. Internet Activities Board, April 1992. 74. R.L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120--126, February 1978. 75. C.P. Schnorr. Efficient identification and signatures for smart cards. In Advances in Cryptology --- Crypto '89, pages 239--251, Springer-Verlag, New York, 1990. 76. M. Shand and J. Vuillemin. Fast implementations of RSA cryptography. In Proceedings of the 11th IEEE Symposium on Computer Arithmetic, pages 252--259, IEEE Computer Society Press, Los Alamitos, CA, 1993. 77. R.D. Silverman. The multiple polynomial quadratic sieve. Math. Comp., 48:329--339, 1987. 78. M.E. Smid and D.K. Branstad. Response to comments on the NIST proposed Digital Signature Standard. In Advances in Cryptology --- Crypto '92, Springer-Verlag, New York, 1993. 79. J.G. Steiner, B.C. Neuman, and J.I. Schiller. Kerberos: an authentication service for open network systems. In Usenix Conference Proceedings, pages 191--202, Dallas, Texas, February 1988. 80. M.J. Wiener. Efficient DES key search. August 20, 1993. Presented at Crypto '93 rump session. -------------------------------------------- RSA Laboratories is the research and consultation division of RSA Data Security, Inc., the company founded by the inventors of the RSA public-key cryptosystem. RSA Laboratories reviews, designs and implements secure and efficient cryptosystems of all kinds. Its clients include government agencies, telecommunications companies, computer manufacturers, software developers, cable TV broadcasters, interactive video manufacturers, and satellite broadcast companies, among others. For more information about RSA Laboratories, call or write to RSA Laboratories 100 Marine Parkway Redwood City, CA 94065 (415) 595-7703 (415) 595-4126 (fax) PKCS, RSAREF and RSA Laboratories are trademarks of RSA Data Security, Inc. All other trademarks belong to their respective companies. This document is available in ASCII, Postscript, and Latex formats via anonymous FTP to rsa.com:/pub/faq. Please send comments and corrections to faq-editor@rsa.com. === DISTRIBUTION: How to obtain this document This document has been brought to you in part by CRAM, involved in the redistribution of valuable information to a wider USENET audience (see below). The most recent version of this document can be obtained via the author's instructions above. The following directions apply to retrieve the possibly less-current USENET FAQ version. FTP --- This FAQ is available from the standard FAQ server rtfm.mit.edu via FTP in the directory /pub/usenet/news.answers/cryptography-faq/rsa/ Email ----- Email requests for FAQs go to mail-server@rtfm.mit.edu with commands on lines in the message body, e.g. `help' and `index'. Usenet ------ This FAQ is posted every 21 days to the groups sci.crypt talk.politics.crypto alt.security.ripem sci.answers talk.answers alt.answers news.answers === CRAM: the Cyberspatial Reality Advancement Movement In an effort to bring valuable information to the masses, and as a service to motivated information compilers, I (L. Detweiler) will help others unfamiliar with Usenet `publish' their documents for widespread dissemination via the FAQ structure, and act as a `sponsor' knowledgable in the submissions process. This document is being distributed under this arrangement. I have found these compilations tend to appear on various mailing lists and are valuable enough to deserve wider distribution. If you know of an existing compilation of Internet information that is not currently a FAQ, please contact me and I may `sponsor' it. The benefits to the author include: - use of the existing FAQ infrastructure for distribution: - automated mail server service - FTP archival - automated posting - a far wider audience that can improve the quality, accuracy, and coverage of the document enormously through email feedback - potential professional inquiries for the use of your document in other settings, such as newsletters, books, etc. - with me as your sponsor, I will also take care of the technicalities in the proper format of the posted version and updating procedures, leaving you free of the `overhead' to focus on the basic updates alone Send comments relating to the *distribution* of this document (particularly relevant newsgroups not currently covered in its current distribution) or inquiries on other documents to <ld231782@longs.lance.colostate.edu>. The choice of who I `sponsor' is entirely arbitrary. You always have the option of handling the submission process yourself. See the FAQ submission guidelines FAQ in news.answers.